package com.lzq.leetcode.bat;

import java.util.HashMap;
import java.util.Map;

public class LRUWithTTL {
    static class Node {
        int key, value;
        long expireTime;
        Node prev, next;
        public Node(int key, int value, long expireTime) {
            this.key = key;
            this.value = value;
            this.expireTime = expireTime;
        }
    }
    static class DoubleList {
        Node head, tail;
        int size;
        public DoubleList() {
            head = new Node(0, 0, 0);
            tail = new Node(0, 0, 0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }
        public void addLast(Node x) {
            x.prev = tail.prev;
            x.next = tail;
            tail.prev.next = x;
            tail.prev = x;
            size++;
        }
        public void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }
        public Node removeFirst() {
            if (head.next == tail) return null;
            Node first = head.next;
            remove(first);
            return first;
        }
        public int size() {
            return size;
        }
    }
    public static class LRUCache {
        Map<Integer, Node> map;
        DoubleList cache;
        int capacity;
        long ttl;
        public LRUCache(int capacity, long ttl) {
            this.capacity = capacity;
            this.ttl = ttl;
            map = new HashMap<>();
            cache = new DoubleList();
        }
        public void makeRecently(int key) {
            Node x = map.get(key);
            if (x.expireTime < System.currentTimeMillis()) {
                deleteKey(key);
                return;
            }
            cache.remove(x);
            cache.addLast(x);
        }
        public void addRecently(int key, int value) {
            long expireTime = System.currentTimeMillis() + ttl;
            Node x = new Node(key, value, expireTime);
            cache.addLast(x);
            map.put(key, x);
        }
        public void deleteKey(int key) {
            Node x = map.get(key);
            cache.remove(x);
            map.remove(key);
        }
        public void removeLeastRecently() {
            Node x = cache.removeFirst();
            if (x != null) map.remove(x.key);
        }
        public int get(int key) {
            if (!map.containsKey(key)) return -1;
            Node x = map.get(key);
            if (x.expireTime < System.currentTimeMillis()) {
                deleteKey(key);
                return -1;
            }
            makeRecently(key);
            return x.value;
        }
        public void put(int key, int value) {
            if (map.containsKey(key)) {
                deleteKey(key);
                addRecently(key, value);
                return;
            }
            if (cache.size() == capacity) {
                removeLeastRecently();
            }
            addRecently(key, value);
        }

    }

    public static void main(String[] args) throws InterruptedException {
        LRUCache cache = new LRUCache(2, 2000); // 容量为2，TTL为2秒
        cache.put(1, 100);
        cache.put(2, 200);
        System.out.println(cache.get(1)); // 输出 100
        Thread.sleep(2500); // 等待2.5秒
        System.out.println(cache.get(1)); // 输出 -1（过期）
        cache.put(3, 300);
        System.out.println(cache.get(3)); // 输出 300
    }
}
